#include <stdio.h>
#include <stdlib.h>

int n;  // 物品数量
float capacity;  // 背包容量
float w[50];
float v[50];
float cw = 0;
float cv = 0;
float bestv = 0;
int x[50];  // 物品是否装入
int bestpath[50];  // 最佳路径
int number[50];  // 物品编号

int sorted();
float func_r(int i);
int backtrace(int i);
int print();

int main(int argc, char const* argv[]) {
	int i;
	printf("enter n&&c for goods num: ");
	scanf("%d %f", &n, &capacity);
	printf("w[]: ");
	for (i = 1; i <= n; ++i) {
		scanf("%f", &w[i]);
		number[i] = i;
	}
	printf("v[]: ");
	for (i = 1; i <= n; ++i) {
		scanf("%f", &v[i]);
	}
	sorted();
	backtrace(1);
	print();
	return 0;
}

int sorted() {
	int i, j;
	int max;
	float temp = 0;
	for (i = 1; i < n; ++i) {
		max = i;
		for (j = i+1; j <= n; ++j) {
			if (v[max] / w[max] < v[j] / w[j])
				max = j;
		}
		temp = w[i];
		w[i] = w[max];
		w[max] = temp;

		temp = v[i];
		v[i] = v[max];
		v[max] = temp;

		temp = number[i];
		number[i] = number[max];
		number[max] = temp;
	}

	return 0;
}

int backtrace(int i) {
	int j;
	if (i > n) {
		if (cv > bestv) {
			bestv = cv;
			for (j = 1; j <= n; ++j) {
				bestpath[j] = x[j];
			}
		}
		return 0;
	}

	if (w[i] + cw <= capacity) {
		x[i] = 1;
		cw += w[i];
		cv += v[i];
		backtrace(i+1);
		cw -= w[i];
		cv -= v[i];
	}
	if (func_r(i) > bestv) {
		x[i] = 0;
		backtrace(i+1);
	}
}

// 上界函数：不选择第i个物品时改变b
float func_r(int i) {
	float leftw = capacity - cw;
	float b = cv;

	while (i+1 <= n && w[i+1] <= leftw) {
		leftw -= w[i+1];
		b += v[i+1];
		++i;
	}

	if (i+1 <= n) 
		b += v[i+1] / w[i+1] * leftw;
	return b;
}

int print() {
	int i;
	printf("best chioce: { ");
	for (i = 1; i <= n; ++i) {
		if (bestpath[i] == 1)
			printf("%d ", number[i]);
	}
	printf("}\n");
	printf("best value: %.2f\n", bestv);

	return 0;
}